/**
 * 
 */
package combinatorics.passed;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * @author xyyi
 *
 */
public class Permutation {

	/**
	Permutations
	Given a collection of numbers, return all possible permutations.

	For example,
	[1,2,3] have the following permutations:
	[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
	 */
	public ArrayList<ArrayList<Integer>> permute(int[] num) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		if (num != null && num.length != 0)
			permute(num, 0, list);
		return list;
	}

	public void permute(int[] num, int index, ArrayList<ArrayList<Integer>> list) {
		if (num.length == index) {
			ArrayList<Integer> buffer = new ArrayList<Integer>(num.length);
			for (int i = 0; i < num.length; i++) {
				buffer.add(num[i]);
			}
			list.add(buffer);
		} else {
			for (int i = index; i < num.length; i++) {
				swap(num, i, index);
				permute(num, index + 1, list);
				swap(num, i, index);
			}
		}
	}

	public ArrayList<ArrayList<Integer>> permute1(int[] num) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		if (num != null && num.length != 0) {
			boolean[] visited = new boolean[num.length];
			permute1(num, 0, visited, list, new ArrayList<Integer>());
		}
		return list;
	}

	public void permute1(int[] num, int index, boolean[] visited,
			ArrayList<ArrayList<Integer>> list, ArrayList<Integer> buffer) {
		if (index == num.length) {
			list.add(new ArrayList<Integer>(buffer));
		} else {
			for (int i = 0; i < num.length; i++) {
				if (!visited[i]) {
					visited[i] = true;
					buffer.add(num[i]);
					permute1(num, index + 1, visited, list, buffer);
					buffer.remove(buffer.size() - 1);
					visited[i] = false;
				}
			}
		}
	}

	/**
	Permutations II
	Given a collection of numbers that might contain duplicates, return all possible unique permutations.

	For example,
	[1,1,2] have the following unique permutations:
	[1,1,2], [1,2,1], and [2,1,1].
	 */
	// FAIL to pass leetcode
	public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		if (num == null || num.length == 0)
			return list;

		Arrays.sort(num);// may need to create a new arrya
		permuteUnique(num, 0, list);
		return list;
	}

	public void permuteUnique(int[] num, int index,
			ArrayList<ArrayList<Integer>> list) {
		if (num.length == index) {
			ArrayList<Integer> buffer = new ArrayList<Integer>(num.length);
			for (int i = 0; i < num.length; i++) {
				buffer.add(num[i]);
			}
			list.add(buffer);
		} else {
			for (int i = index; i < num.length; i++) {
				if (i != index
						&& (num[i] == num[index] || num[i] == num[i - 1])) {
					continue;
				}
				swap(num, i, index);
				permuteUnique(num, index + 1, list);
				swap(num, i, index);
			}
		}
	}

	private void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	// good for interview
	public ArrayList<ArrayList<Integer>> permuteUnique1(int[] num) {
		//assume no duplicates
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if (num != null && num.length > 0) {
			Arrays.sort(num);
			boolean[] visited = new boolean[num.length];
			permuteUnique1(num, 0, visited, result, new ArrayList<Integer>());
		}
		return result;
	}

	public void permuteUnique1(int[] num, int index, boolean[] visited,
			ArrayList<ArrayList<Integer>> result, ArrayList<Integer> buffer) {
		if (num.length == index) {
			result.add(new ArrayList<Integer>(buffer));
		} else {
			for (int i = 0; i < num.length; i++) {
				if (!visited[i]) {
					if (i > 0 && num[i] == num[i - 1] && !visited[i - 1])
						continue;
					visited[i] = true;
					buffer.add(num[i]);
					permuteUnique1(num, index + 1, visited, result, buffer);
					buffer.remove(buffer.size() - 1);
					visited[i] = false;
				}
			}
		}
	}

	/**
	 * 
	 */
	public Permutation() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Permutation p = new Permutation();

		int[] num = { 0, 1, 0, 0, 9 };
		//int[] num = { 1 };
		//ArrayList<ArrayList<Integer>> result = p.permuteUnique(num);
		ArrayList<ArrayList<Integer>> result1 = p.permuteUnique(num);
		p.print(result1);
	}

	public void printDulipcate(ArrayList<ArrayList<Integer>> result) {
		System.out.printf("Total: %d\n", result.size());
		HashSet<ArrayList<Integer>> hash = new HashSet<ArrayList<Integer>>();
		for (ArrayList<Integer> arr : result) {
			if (hash.contains(arr)) {
				for (Integer i : arr) {
					System.out.printf("%d,", i);
				}
				System.out.println();
			} else {
				hash.add(arr);
			}
		}

		System.out.println();
	}

	private void print(ArrayList<ArrayList<Integer>> result) {
		System.out.printf("Total: %d\n", result.size());
		for (ArrayList<Integer> arr : result) {
			for (Integer i : arr) {
				System.out.printf("%d,", i);
			}
			System.out.println();
		}
	}
}
